class Solution1 {
    public int deleteAndEarn(int[] nums) {
        // 预处理
        int n = 10001;
        // arr[i]表示i出现的总和
        int[] arr = new int[n];
        for (int x : nums) {
            arr[x] += x;
        }
        // 打家劫舍
        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = arr[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]);
        }
        return dp[n - 1];
    }
}